#include <bits/stdc++.h>
using namespace std;

/*
2012. 数组美丽值求和
已解答
中等
相关标签
相关企业
提示
给你一个下标从 0 开始的整数数组 nums 。对于每个下标 i（1 <= i <= nums.length - 2），nums[i] 的 美丽值 等于：

2，对于所有 0 <= j < i 且 i < k <= nums.length - 1 ，满足 nums[j] < nums[i] < nums[k]
1，如果满足 nums[i - 1] < nums[i] < nums[i + 1] ，且不满足前面的条件
0，如果上述条件全部不满足
返回符合 1 <= i <= nums.length - 2 的所有 nums[i] 的 美丽值的总和 。

 

示例 1：

输入：nums = [1,2,3]
输出：2
解释：对于每个符合范围 1 <= i <= 1 的下标 i :
- nums[1] 的美丽值等于 2
示例 2：

输入：nums = [2,4,6,4]
输出：1
解释：对于每个符合范围 1 <= i <= 2 的下标 i :
- nums[1] 的美丽值等于 1
- nums[2] 的美丽值等于 0
示例 3：

输入：nums = [3,2,1]
输出：0
解释：对于每个符合范围 1 <= i <= 1 的下标 i :
- nums[1] 的美丽值等于 0
 

提示：

3 <= nums.length <= 105
1 <= nums[i] <= 105
*/

// 法一
class Solution {
public:
	int sumOfBeauties(vector<int>& nums) {
		int n = nums.size();
		vector<int> lmax(n), rmin(n);
		// 左侧最大值数组
		lmax[0] = nums[0];
		for(int i = 1; i < n; ++i) {
			lmax[i] = max(lmax[i - 1], nums[i]);
		}
		// 右侧最小
		rmin[n - 1] = nums[n - 1];
		for(int i = n - 2; i >= 0; --i) {
			rmin[i] = min(rmin[i + 1], nums[i]);
		}

		int ans = 0;
		for(int i = 1; i < n - 1; ++i){
			if(lmax[i - 1] < nums[i] && nums[i] < rmin[i + 1]) {
				ans += 2;
			} else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) {
				ans += 1;
			}
		}
		return ans;
	}
};

// 法二
class Solution {
	public:
	int sumOfBeauties(vector<int>& nums) {
		// 预处理右侧最小值数组：marr[i]表示i位置右侧最小值
		// 时间复杂度O(n)预处理，替代暴力嵌套循环的O(n²)复杂度[2,3](@ref)
		int length = nums.size();
		int* marr = new int[length];  // 使用原生数组减少vector容器开销[4](@ref)
		int fmax = nums[0];           // 动态维护左侧最大值，避免额外数组存储
		int sum = 0;

		// 从右向左预处理最小值数组（关键优化点）
		marr[length - 1] = nums[length - 1];
		for (int i = length - 2; i >= 0; i--) {
			marr[i] = min(marr[i + 1], nums[i]);  // 递推式预处理
		}

		// 单次遍历计算美丽值（时间复杂度O(n)）
		for (int i = 1; i < length - 1; i++) {
			// 条件1：满足严格递增递减全局条件（美丽值+2）
			if (nums[i] > fmax && nums[i] < marr[i + 1]) {
				sum += 2;
			}
			// 条件2：仅满足局部递增条件（美丽值+1）
			else if (nums[i] > nums[i - 1] && nums[i] < nums[i + 1]) {
				sum += 1;
			}
			// 动态更新左侧最大值（优化空间复杂度为O(1)）
			fmax = max(fmax, nums[i]);
		}
		delete[] marr;  // 注意释放动态内存（建议改用unique_ptr更安全）
		return sum;
	}
};